1. Field of the Invention
The present invention is related generally to the field of image encoding and more particularly to JPEG compression/decompression schemes and methods. It is specifically directed to a methodology of production of low resolution thumbnails directly, at low cost, without doing a full JPEG decompression.
2. Discussion of the Prior Art
The Joint Photographic Experts Group (JPEG) has promulgated a standard for still image compression, known as the JPEG standard, which employs a Discrete Cosine Transform-based algorithm. The JPEG standard is described in a number of publications, including the following references the contents and disclosures of which are incorporated by reference herein: Wallace, "The JPEG Still Picture Compression Standard," IEEE Transactions on Consumer Electronics, Vol. 34, No. 4, pp. 30-44 (April, 1991); Feig, E., and Winograd, S., "Fast algorithms for the discrete cosine transform," IEEE Trans. on Signal Processing., Vol. 40, no. 9, pp. 2174-2193, (September, 1992). Stone, H. S., "Progressive wavelet correlation using Fourier methods," Submitted for publication to IEEE Trans. on Signal Processing, 1996.
As shown in FIG. 1(a), in the JPEG compression method implementing sequential encoding, the original image is divided into blocks of pixels, each block typically containing 8.times.8 or 16.times.16 original image samples. Each 8.times.8 block of pixels is input to a DCT-encoder element 10 having a forward discrete cosine transform processor 12 that performs a Discrete Cosine Transform (DCT) on each pixel block, producing a representation of the input block as DCT coefficients corresponding to frequencies and amplitudes, rather than corresponding directly to color information. These coefficients are then quantized, or rounded off, by a quantizer element 14 in accordance with a quantization table 16, and DC coding is performed that employs a difference algorithm over all quantized blocks in the image, in a selected scan order. This difference algorithm subtracts a "DC" or zero frequency term corresponding to the mean pixel value of a block, from the DC term of the preceding block. The difference coefficients are then scanned in a different order, such as a zigzag order, and the non-zero coefficients (i.e., blocks in which a difference from the preceding block occurred) are coded to indicate the number of preceding zero coefficients (i.e., the number of pixel blocks in which no change occurred) and also the value of the non-zero difference. An additional compression step known as entropy encoding is performed by encoder element 18 to achieve a more compact coding of the quantized DCT elements. Entropy encoding schemes specified by the JPEG standard include Huffman coding and arithmetic coding, with the optional implementation of entropy encoding tables 19. The output 20 of the DCT encoder 10 is a data stream of compressed image data.
It should be understood that the key feature of JPEG compression is that an image is first segmented into disjoint 8.times.8 pixel blocks, each of which is replaced by its 2-D DCT. In such a representation, the high frequencies tend to have very small coefficients enabling JPEG quantization to drive most of these coefficients to zero. This enables fewer bits to be stored after encoding.
Decompression is performed by reversing the compression process, producing the displayable image. As shown in FIG. 1(b), this typically involves inputting the compressed image data into a DCT decoder including an entropy decoder block 27 for decoding the compressed image data stream, e.g., in accordance with a Huffman decoding technique. At the output of the entropy decoder the same data structure that the encoder 10 had at the end of the DCT transform is created. Then, a dequantization block 28 for dequantizing the image samples, and an inverse discrete cosine transform processor 29 for performing an inverse discrete cosine transform taking the decoded 64 DCT coefficients and reconstructing the original image.
Besides the sequential encoding method described, the JPEG standard sets forth other largely incompatible encoding techniques. For instance, in a progressive encoding technique, the image is encoded in multiple scans for applications in which the transmission time is long and viewers prefer to watch the image build up in multiple coarse-to-clear passes. In hierarchical encoding, the image is encoded at multiple resolutions, so that lower-resolution versions may be accessed without first having to decompress the image at its full resolution. Particularly, the hierarchical mode implements "pyramidal" encoding of an image at multiple resolutions, each differing in resolution from its adjacent encoding, e.g., by a factor of two, in either horizontal or vertical dimensions or both. While enabling multiple decompression levels, the hierarchical scheme set forth in the standard requires that each additional level be stored in the compressed image.
As is known, the usefulness of decompression algorithms is determined by the number and the speed of mathematical computations performed to obtain the identifiable decompressed image. Typically, in image searching applications, it is required that each image is fully decompressed before the target image is located, which is a costly proposition as many computations are required to achieve full decompression.
It would thus be highly desirable to provide a means for achieving intermediate levels of decompression of a compressed JPEG image without having to encode the image at multiple resolutions.
Furthermore, it would be desirable to achieve multiple levels of decompression of an image that has been encoded according to the sequential (lossy) encoding standard. In such a technique, one or more decompressed "thumbnail" images may be produced, each thumbnail being observable and useful for searching applications, without the necessity of achieving full JPEG decompression of the original image.